首先这道题要用到以下知识:
并查集、圆与圆的位置关系(可推广到球与球)、空间两点坐标公式
空间两点坐标公式体面给了,这里不讲。
先讲圆与圆的位置关系判定:
如图,从上到下,从左到右依次是:外离,外切,相交,内切,内含
设两圆圆心距离为$d(d>0)$,半径为$r_1$、$r_2$
则有以下关系:
外离:$d>r_1+r_2$
外切:$d=r_1+r_2$
相交:$|r_1-r_2|<d<r_1+r_2$
内切:$d=|r_1-r_2|$
内含:$d<|r_1-r_2|$
此结论可以直接推广至球与球的位置关系。
对于本题,我们只需要考虑外离、相切、相交三种情况,内切和内含可略去(没有意义)。
题中默认$z$轴正方向向上,$x$轴、$y$轴随意(不影响)
我的思路是:
每个球各化为一点,
顶层底层各是一点,
若相切相交即为合并,
最后再验顶底同祖宗。
对于此题,除了用上外离、外切、相交的判定外,还有:
若$z-r<=0$,则该球与底部相交/相切。
若$z+r>=h$,则该球与顶部相交/相切。
贴代码,附解析:
1 | /* |